The present invention relates to the production of long period pseudo-random binary signal sequences.
Pseudo-random sequences of binary signals are used in modern information processing techniques for various purposes. They are employed, for example, as noise signals, as test signals for transmission paths, and as code sequences for encoding information.
For the latter cases it is necessary to have pseudo-random sequences of binary signals of extremely long period durations which can be formed simultaneously, i.e. in rigid phase relationship, at the transmitting end as well as at the receiving end with the aid of a program. The laws for forming such sequences must be complex enough that no matter how long the sequence of bits to be received and evaluated, the further continuation of the bit sequence under consideration must not be predictable with the aid of modern computer systems.
Methods and circuits are known for producing pseudo-random binary signal sequences employing binary counters or feedback connected shift registers. Sufficiently long periods can be produced with relatively low cost circuits by suitable linkage of the signals from a plurality of counters or shift registers if the period durations of the pulse sequences furnished by the individual counters or shift registers have no common divisor with one another. After linkage, there then results a total period duration which is equal to the product of the lengths of the periods or of the partial pulse sequences furnished to the individual counters or shift registers, respectively. The period duration is usually given by the number of binary bits within one period.
More or less complex linkage circuits produce from the partial pulse sequences a total pulse sequence with pseudo-random properties. Statistical testing processes can be used to determine certain characteristics of a pseudo-random pulse sequence, and thus the degree to which such a pulse sequence approximates the ideal case of a true random sequence can be measured.
There are already a number of disclosures, for example in German Offenlegungsschrift (Laid-Open Application) No. 2,341,627, British Patent No. 1,155,546 and U.S. Pat. No. 3,515,805, of procedures for coding data, i.e. pulse sequences, by means of so-called "scramblers," which in this particular case are understood to mean linearly feedback connected shift registers through which the text to be coded or decoded is channeled. With the same shift register arrangement as at the transmitting end, it is possible to cancel out the coding at the receiving end.
Such an arrangement is not suited for a higher degree of coding since when an N position shift register is used it will be possible to calculate the length and type of connection of the feedback connected shift register on the basis of 2N received bits and thus to break the code. German Auslegeschrift (Published Application) No. 1,537,062 discloses a code generator in which "scramblers", which can also be described as shift register converters, are used to improve pseudo-random "primary" pulse sequences by converting them to "secondary sequences." The operating sequence of the shift register, which is originally given by the feedback loop, is interfered with by the primary pulse sequences fed thereinto so that the shift register emits a new secondary sequence having a longer duration. The drawback of this arrangement is that the resulting improvement can systematically be cancelled out by simulation of the shift register arrangement, so that also in this case the characteristics of the primary sequence can be recognized to enable the operator to break the code.
German Auslegeschrift No. 1,257,843 also discloses a code generator in which one or a plurality of shift registers are provided which are connected into a ring and whose individual stages are connected together via so-called mixers. Signals obtained from the terminals of a binary counter chain are fed into these mixers in dependence on various state criteria. A long counter chain and a long shift register are provided to produce a pseudo-random behavior of the sequence circulating in the shift register. However, the signals at the terminals of a counter chain are not independent of one another and thus a greater or lesser amount of subperiods will occur within the total period so that the result no longer has the required random characteristic.
The desired properties of pseudo-random binary signal sequences, briefly outlined above, i.e. long duration, e.g. &gt;10.sup.30 bits; statistical test behavior, i.e. approaching genuinely random sequences; a plurality of setting possibilities by means of programs; complex laws for formation; repeatability; high operating speed; and possibility for realizing them with economically justifiable expenditures, cannot be met entirely by any of the known solutions with a sufficient degree of dependability.